package main.Q1401_1500;

import java.util.Arrays;

public class Q1491_1500 {
    public static void main(String[] args) {
        System.out.println("Question1491：去掉最低工资和最高工资后的平均值");
        System.out.println("Question1492：");
        System.out.println("Question1493：删掉一个元素以后全为 1 的最长子数组");
        System.out.println("Question1494：");
        System.out.println("Question1495：");
        System.out.println("Question1496：");
        System.out.println("Question1497：");
        System.out.println("Question1498：满足条件的子序列数目");
        System.out.println("Question1499：");
        System.out.println("Question1450：");
    }
}

class Question1491 {
    public double average(int[] salary) {
        double avg = 0;
        int max = salary[0], min = salary[0], total = 0;
        for (int money : salary) {
            total += money;
            max = Math.max(max, money);
            min = Math.min(min, money);
        }
        total -= max + min;
        avg = (total * 1.0) / (salary.length - 2);
        return avg;
    }
}

class Question1493 {
    public int longestSubarray(int[] nums) {
        int[] leftLength = new int[nums.length], rightLength = new int[nums.length];
        leftLength[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            leftLength[i] = nums[i] == 0 ? 0 : leftLength[i - 1] + 1;
        }
        rightLength[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            rightLength[i] = nums[i] == 0 ? 0 : rightLength[i + 1] + 1;
        }
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int preSum = i == 0 ? 0 : leftLength[i - 1];
            int sufSum = i == nums.length - 1 ? 0 : rightLength[i + 1];
            result = Math.max(result, preSum + sufSum);
        }
        return result;
    }
}

class Question1498 {
    public int process(int[] nums, int start, int target) {
        int index = -1, length = nums.length;
        if (nums[start] > target) {//最小值大于目标值
            return index;
        } else {
            int left = start, right = length;
            while (left < right) {//寻找满足条件的最大值
                int mid = left + (right - left) / 2;
                if (nums[mid] <= target) left = mid + 1;
                else right = mid;
            }
            index = left - 1;
        }
        return index;
    }

    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        final int mod = (int) 1e9 + 7;
        int count = 0;
        int[] pow = new int[nums.length];
        pow[0] = 1;
        for (int i = 1; i < nums.length; i++) pow[i] = pow[i - 1] * 2 % mod;
        for (int i = 0; i < nums.length; i++) {
            int maxIndex = process(nums, i, target - nums[i]);
            if (maxIndex != -1) {//子序列数
                count = (count + pow[maxIndex - i]) % mod;
            }
        }
        return count % mod;
    }
}